package com.example.algorithm.backtrcaking;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/18
 * 分割回文数
 */
public class Division {

    List<List<String>> list=new ArrayList<>();
    Deque<String> deque=new LinkedList<>();
    public List<List<String>> partition(String s) {
        backTracking(s,0);
        return list;
    }

    private void backTracking(String s, int startIndex) {
        if(startIndex>=s.length()){
            list.add(new ArrayList<>(deque));
            return;
        }
        for(int i=startIndex;i<s.length();i++)
        {
            if(isPalindrome(s,startIndex,i)) {
                String abc=s.substring(startIndex,i+1);
                deque.addLast(abc);
            }else {
                continue;
            }
            backTracking(s,i+1);
            deque.removeLast();
        }
    }

    private boolean isPalindrome(String s, int startIndex, int end) {
        for(int i=startIndex,j=end;i<j;i++,j--)
        {
            if(s.charAt(i)!=s.charAt(j))
            {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        Division division = new Division();
        String abc="aab";
        List<List<String>> partition = division.partition(abc);
        partition.stream().forEach(System.out::println);
    }


}
